// 背包问题背包的大小一定会作为一个维度

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    int backPack(int m, vector<int> &A) {
        int n = A.size();
        // vector<vector<bool>> rec(n + 1, vector<bool>(m + 1)); //前i个物品能否拼出重量j
        // rec[0][0] = true;
        // for (int i = 1; i < n + 1; ++i) {
        //     for (int j = 0; j < m + 1; ++j) {
        //         rec[i][j] = rec[i - 1][j]; // 第i个不放进背包，判断i-1个能不能装到大小j
        //         if (j >= A[i - 1]) // 第i个放进背包，判断i-1个能不能装到大小j - A[i]
        //             rec[i][j] = rec[i][j] || rec[i - 1][j - A[i - 1]];
        //     }
        // }
        // for (int i = m; i >= 0; --i) {
        //     if (rec[n][i]) return i;
        // }

        // 第i步的状态只与第i-1步有关，可以用一维数组解，从后往前算，
        // 这样rec[j - A[i]]还是上一层的状态。如果从前往后，rec[j - A[i]]先算出来了，已经是当前层的状态了

        // 基于一维数组做反向迭代，反向迭代能避免重复取
        vector<int> rec(m + 1, 0); //背包大小为i时的最大重量
        for (int i = 0; i < A.size(); ++i) {
            for (int j = m; j >= A[i]; --j) {
                rec[j] = max(rec[j], rec[j - A[i]] + A[i]);
            }
        }
        return rec.back();
    }
};